package com.sheng.leetcode.year2025.month10.day11;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author by ls
 * @date 2025/10/11
 * <p>
 * 3186. 施咒的最大总伤害<p>
 * <p>
 * 一个魔法师有许多不同的咒语。<p>
 * 给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。<p>
 * 已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。<p>
 * 每个咒语最多只能被使用 一次 。<p>
 * 请你返回这个魔法师可以达到的伤害值之和的 最大值 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：power = [1,1,3,4]<p>
 * 输出：6<p>
 * 解释：<p>
 * 可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：power = [7,1,6,6]<p>
 * 输出：13<p>
 * 解释：<p>
 * 可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。<p>
 * <p>
 * 提示：<p>
 * 1 <= power.length <= 10^5<p>
 * 1 <= power[i] <= 10^9<p>
 */
public class LeetCode3186 {

    @Test
    public void test() {
        int[] power = {1, 1, 3, 4};
//        int[] power = {7, 1, 6, 6};
        System.out.println(new Solution().maximumTotalDamage(power));
    }
}

class Solution {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : power) {
            // cnt[x]++
//            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            cnt.merge(x, 1, Integer::sum);
        }

        int n = cnt.size();
        int[] a = new int[n];
        int k = 0;
        for (int x : cnt.keySet()) {
            a[k++] = x;
        }
        Arrays.sort(a);

        long[] memo = new long[n];
        // -1 表示没有计算过
        Arrays.fill(memo, -1);
        return dfs(a, cnt, memo, n - 1);
    }

    private long dfs(int[] a, Map<Integer, Integer> cnt, long[] memo, int i) {
        if (i < 0) {
            return 0;
        }
        // 之前计算过
        if (memo[i] != -1) {
            return memo[i];
        }

        int x = a[i];
        int j = i;
        while (j > 0 && a[j - 1] >= x - 2) {
            j--;
        }
        return memo[i] = Math.max(dfs(a, cnt, memo, i - 1), dfs(a, cnt, memo, j - 1) + (long) x * cnt.get(x));
    }
}
